package sword.offer;

import sword.offer.common.TreeNode;

import java.util.Arrays;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 * 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Seven {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.buildTree(new int[]{1,2}, new int[]{1,2});
    }
    static class Solution {
        int pIndex;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return putUpTree(preorder, inorder, 0, inorder.length-1);
        }

        TreeNode putUpTree(int[] preorder, int[] inorder, int startIndex, int finishIndex){
            if(finishIndex - startIndex < 0){
                return null;
            }
            TreeNode node = new TreeNode(preorder[pIndex]);
            int i = startIndex;
            // 找到这个根节点在中序遍历的位置
            for (; i <= finishIndex; i++) {
                if(inorder[i] == preorder[pIndex]){
                    break;
                }
            }
            pIndex++;
            node.left = putUpTree(preorder, inorder, startIndex, i-1);
            node.right = putUpTree(preorder, inorder,  i+1, finishIndex);
            return node;
        }
    }
}
